package treesNgraphs;

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

/**
 * Created by Tzachi on 21/10/2014.
 */
public class DfsSearch {
    public static void dfs_iter(Graph graph, int startNode, int targetNode) {
        Set<Integer> visited = new HashSet<>();
        Stack<Integer> stack = new Stack<>();
        stack.push(startNode);
        while (!stack.isEmpty()){
            int currentNode = stack.pop();
            visited.add(currentNode);
            if (currentNode == targetNode){
                // Do something
                // break?
            }
            for (Graph.Edge neighbour: graph.getAllNeighbours(currentNode)){
                if (!visited.contains(neighbour.getDestinationVertex())){
                    stack.push(neighbour.getDestinationVertex());
                }
            }
        }
    }

    public static void dfs_recursive(Graph graph, Set<Integer> visited, int currentNode, int targetNode){
        visited.add(currentNode);
        if (currentNode == targetNode){
            // Do something
            // break?
        }
        for (Graph.Edge neighbour: graph.getAllNeighbours(currentNode)){
            if (!visited.contains(neighbour.getDestinationVertex())){
                dfs_recursive(graph, visited, neighbour.getDestinationVertex(), targetNode);
            }
        }
    }

}
